package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC221 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maximalSquare(char[][] arr) {
            if (null == arr || arr.length <= 0) return 0;

            int curMax = Integer.MIN_VALUE;
            int dp[][] = new int[arr.length][arr[0].length];
            for (int i = 0; i < arr.length; i++) {
                dp[i][0] = arr[i][0] == '1' ? 1 : 0;
                curMax = curMax < dp[i][0] ? dp[i][0] : curMax;
            }
            for (int j = 1; j < arr[0].length; j++) {
                dp[0][j] = arr[0][j] == '1' ? 1 : 0;
                curMax = curMax < dp[0][j] ? dp[0][j] : curMax;
            }

            for (int i = 1; i < arr.length; i++) {
                for (int j = 1; j < arr[0].length; j++) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]);
                    dp[i][j] = arr[i][j] == '0' ? 0 : 1 + dp[i][j];
                    curMax = dp[i][j] > curMax ? dp[i][j] : curMax;
                }
            }

            return curMax * curMax;
        }
    }

    public void run() {
        Solution solution = new Solution();
        char[][] arr = InputUtil.toDoubleCharArray("[[\"1\",\"0\",\"1\",\"1\",\"0\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\",\"1\"],[\"0\",\"1\",\"1\",\"0\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"0\",\"1\",\"0\"],[\"0\",\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"0\",\"1\",\"1\",\"1\"]]");

        System.out.println(solution.maximalSquare(arr));
    }

    public static void main(String[] args) throws Exception {
        LC221 an = new LC221();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
